package binarySearch;

/**
 * 剑指 Offer 53 - II. 0～n-1中缺失的数字
 * 从0,1,2,...,n这n+1个数中选择n个数，组成有序数组（不重复），找出这n个数中缺失的那个数，要求O(n)尽可能小。
 * [0,1,2,3,4,5,7]
 * 缺失 6
 */
public class Solution {

    public static void main(String[] args) {
        int[] array=new int[]{0,1,2,3,4,5};
//        System.out.println(new Solution().missingNumber(array));
        System.out.println(new Solution().binarySearch(array,4));
    }


    /**
     *利用二分查找:当array[i]=i则表示i之前的都是对的那么start就移到mid;如果array[i]>i则表示错误的在左边或者a[i]那么end就移动到temp;
     * 当end-start==1时则end就是错误的，因为如果时start是错误的话后面也是错误的.
     */
    public int missingNumber(int[] array){
        //特殊处理 第一位
        if (array[0]!=0){
            return 0;
        }
        System.out.println(1);
        System.out.println(2);
        System.out.println(3);
        //特殊处理 最后一位
        if (array[array.length-1]==array.length-1){
            return array.length;
        }
        int start=0;
        int end=array.length-1;
        while (true){
            if (end-start==1){
                return end;
            }
            int temp=(start+end)/2;
            if (array[temp]>temp){
                end=temp;
            }else {
                start=temp;
            }
        }
    }

    /**
     * 经典 二分查找
     */
    public int binarySearch(int[] array,int hkey){
        int result=-1;
        int start=0;
        int end=array.length-1;
        while (start<=end){
            int mid=start+(end-start)/2; //防止溢位
            if (hkey>array[mid]){
                start=mid+1;
            }else if (hkey<array[mid]){
                end=mid-1;
            }else {
                result=mid;
                break;
            }
        }
        return result;
    }
}
